/**
 * 链表排序，使用归并
 * 
 */
class SortListGui {
    public ListNode sortList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode fast=head;
        ListNode pre=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
       
            pre.next=null;
        
       ListNode list1=sortList(head);
        ListNode list2=sortList(slow);
        ListNode list= merge(list1,list2);
        return list;
    }
    public ListNode merge(ListNode head1,ListNode head2){
        ListNode newHead=new ListNode(0);
        ListNode cur=newHead;
        while(head1!=null&&head2!=null){
            if(head1.val<head2.val){
                cur.next=head1;
                cur=head1;
                head1=head1.next;
            }
            else{
                cur.next=head2;
                cur=head2;
                head2=head2.next;
            }
        }
        if(head1!=null){
            cur.next=head1;
        }
        if(head2!=null){
            cur.next=head2;
        }
        return newHead.next;
    }

}